package top.interview

import problem.Problem

class Q240Search2dMatrixII extends Problem {

  def searchMatrix(matrix: Array[Array[Int]], target: Int): Boolean = {
    if (matrix.isEmpty || matrix(0).isEmpty) false
    else {
      val n = matrix.length
      val m = matrix(0).length
      search(matrix, target, 0, 0, m - 1, n - 1)
    }
  }

  def search(a: Array[Array[Int]], target: Int, lx: Int, ly: Int, rx: Int, ry: Int): Boolean = {
    val (nlx, nry) = (ly to ry).find(j => a(j)(lx) >= target) match {
      case Some(j) =>
        val y = if (a(j)(lx) == target) j else math.max(0, j - 1)
        (lx, y)
      case None => (lx + 1, ry)
    }
    val (nrx, nly) = (nlx to rx).find(i => a(ly)(i) >= target) match {
      case Some(i) =>
        val x = if (a(ly)(i) == target) i else math.max(0, i - 1)
        (x, ly)
      case None => (rx, ly + 1)
    }
    val exist = (nlx to nrx).exists(i => a(nry)(i) == target) ||
      (nly to nry).exists(j => a(j)(nrx) == target)
    if (exist) true
    else {
      if (nlx <= nrx - 1 && nly <= nry - 1) {
        search(a, target, nlx, nly, nrx - 1, nry - 1)
      } else {
        false
      }
    }
  }

  override def test(): Unit = {
    val a1 = Array(
      Array(1, 4, 7, 11, 15),
      Array(2, 5, 8, 12, 19),
      Array(3, 6, 9, 16, 22),
      Array(10, 13, 14, 17, 24),
      Array(18, 21, 23, 26, 30)
    )

    val a2 = Array(Array(1, 3, 5))

    val a3 = Array(
      Array(1, 3, 5, 7, 9),
      Array(2, 4, 6, 8, 10),
      Array(11, 13, 15, 17, 19),
      Array(12, 14, 16, 18, 20),
      Array(21, 22, 23, 24, 25)
    )

    val a4 = Array(Array(-5))

    val cases = Table(("matrix", "target", "exist"),
      (a1, 5, true), (a1, 20, false), (a1, 13, true),
      (a2, 1, true),
      (a2, 1, true),
      (a3, 13, true),
      (a4, -5, true)
    )

    forAll(cases) { case (matrix, target, exist) =>
      searchMatrix(matrix, target) shouldBe exist
    }
  }
}
